package org.example.myleet.p436;

import java.util.Arrays;
import java.util.Comparator;

public class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        Integer[] order = new Integer[n];
        int[][] copyIntervals = new int[n][2];
        for (int i = 0; i < n; ++i) {
            order[i] = i;
            copyIntervals[i][0] = intervals[i][0];
            copyIntervals[i][1] = intervals[i][1];
        }
        Arrays.sort(order, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return intervals[o1][0] - intervals[o2][0];
            }
        });
        Arrays.sort(copyIntervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int[] result = new int[n];
        for (int i = 0; i < n; ++i) {
            int[] interval = intervals[i];
            int l = 0, r = n;
            while (l < r) {
                int mid = (l + r) >>> 1;
                if (copyIntervals[mid][0] < interval[1]) {
                    l = mid + 1;
                } else if (copyIntervals[mid][0] > interval[1]) {
                    r = mid;
                } else {
                    l = mid;
                    break;
                }
            }
            if (l >= n) {
                result[i] = -1;
            } else {
                result[i] = order[l];
            }
        }
        return result;
    }
}
